#include "Sort_2.h"

//归并排序
void MergeSort(int* a,int n)
{
    int* tmp=(int*)malloc(sizeof(int)*n);//开一个空间去储存排好序的数组然后再复制到原数组中
    if(tmp==NULL)
    {
        perror("Malloc error:");
        exit(-1);
    }
    _MergeSort(a,0,n-1,tmp);
    free(tmp);
    tmp=NULL;
}
void _MergeSort(int* a, int begin, int end,int* tmp )
{
    if(begin>=end)//结束条件
        return;
    int mid=(begin+end)/2;
    int begin1=begin , end1=mid;//分区间
    int begin2=mid+1 , end2=end;
    _MergeSort(a , begin1 , end1 , tmp);//左区间排序
    _MergeSort(a , begin2 , end2 , tmp);//右区间排序

    int i=begin; //tmp的下标
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])//两个区间排序
        {
            tmp[i++] = a[begin1++];//tmp的下标i一直往后走
        }
        else//升序
        {
            tmp[i++] = a[begin2++];
        }
    }

    //当其中一个区间中的值还没被复制完
    while(begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while(begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1));//拷贝数组 
    //     begin每次递归后的位置        闭区间 要+1 如 0～9应该是10个大小
}

//归并非递归
void MergeSortNOR(int* a, int n)
{
    int* tmp=(int*)malloc(sizeof(int)*n);//开一个空间去储存排好序的数组然后再复制到原数组中
    if(tmp==NULL)
    {
        perror("Malloc error:");
        exit(-1);
    }
    int rangeN=1;//归并的个数
    while(rangeN<n)
    {
        for(int i=0;i<n;i+=rangeN*2)
        {
            int begin1=i,end1=i+rangeN-1;//闭区间
            int begin2=i+rangeN,end2=i+rangeN*2-1;//end2=i + rangeN + rangeN-1第二个区间的位置比第一个区间大rangeN个

            int j=i; //tmp的下标
            //修正区间
            if(end1>=n)//第一个区间尾部end1越界
            {
                end1=n-1;//数组末尾
                //不存在的区间 使下面第二个区间的循环不会执行 防止越界
                begin2=n;
                end2=n-1;
            }
            else if(begin2>=n)//第二个区间的头部begin2越界 即这区间整体越界
            {
                //不存在的区间
                begin2=n;
                end2=n-1;
            }
            else if(end2>=n)//第二个区间尾部end2越界
            {
                end2=n-1;//数组末尾
            }
            while(begin1 <= end1 && begin2 <= end2)
            {
                if(a[begin1] < a[begin2])//两个区间排序
                {
                    tmp[j++] = a[begin1++];//tmp的下标j一直往后走
                }
                else//升序
                {
                    tmp[j++] = a[begin2++];
                }
            }

            //当其中一个区间中的值还没被复制完
            while(begin1 <= end1)
            {
                tmp[j++] = a[begin1++];
            }
            while(begin2 <= end2)
            {
                tmp[j++] = a[begin2++];
            }
            //memcpy(a,tmp,sizeof(int)*n);//修正区间后可以整体拷贝数组 也可以局部拷贝 
        }
            memcpy(a,tmp,sizeof(int)*n);//修正区间后可以整体拷贝数组 也可以局部拷贝 
            rangeN*=2;//每次X2 扩大区间
    }
    free(tmp);
    tmp=NULL;
}


//三数取中
int GetMidIndex(int *a,int begin,int end)
{
    //int mid=(begin+end)/2;
    int mid = begin + rand()%(end-begin);
    if(a[begin]>a[mid])
    {
        if(a[mid]>a[end])
        {
            return mid;  //begin> mid >end
        }
        else if (a[begin]>a[end])//begin > mid < end  mid最小 再比较begin和end 
            return end;  //begin> end >mid   
            else         //谁小谁是中间值
            return begin;//end> begin >mid
    }
    else //begin<mid
    {
        if(a[begin]>a[end])
        {
            return begin; //end< begin <mid
        }
        else if(a[mid]>a[end])//mid > begin < end   begin最小 再比较mid和end
            return end;   //mid> end >begin
            else
            return mid;   //begin< mid <end
    }
}

//插入排序
void InsertSort(int* a, int n)
{
   for(int i=0;i<n-1;i++)
   {
    int end=i;
    int tmp=a[end+1];//后面一个
    while(end>=0)
    {
        if(tmp<a[end])
        {
            a[end+1]=a[end];
            end--;
        }
        else
        {
            break;
        }
    }
    a[end+1]=tmp;//升序 当找到比tmp小的数a[end] 那么tmp排在它后面 tmp和a[end+1]交换
   } 
}

//快排 三路划分
void QuickSort(int* a,int begin,int end)//左闭右开
{
    if(begin>=end)  return;
    if((end-begin+1)<15)//小区间优化 ：当区间<15 直接使用插入排序代替 减少递归次数
    {
        InsertSort(a+begin,end-begin+1);
        //1 2 3 4 5 | 4 6 4 3 1 区间在｜后面  排的是｜后的区间数组 所以a+begin
    }
    else
    {
        int mid=GetMidIndex(a,begin,end);
        Swap(&a[begin],&a[mid]);
        int left=begin,right=end;
        int key=a[begin];
        int cur=left+1;
        while(cur<=right)
        {
            if(a[cur]<key)//把比key小的往前推
            {
                Swap(&a[cur],&a[left]);
                cur++;
                left++;
            }
            else if(a[cur]>key)//把比key大的往后推
            {
                Swap(&a[cur],&a[right]);
                right--;
            }
            else //如果==key 就留在中间 区间为第一段和第三段
            {
                cur++;
            }
        }

        QuickSort(a,begin,left-1);//key-1是左区间的最大下标
        QuickSort(a,right+1,end);//right跑到前面去变成第二个区间的首位
    }
}

//计数排序
void CountSort(int* a, int n)
{
    int max = a[0], min = a[0];
    for (int i = 1; i < n; ++i)
    {
        if (a[i] < min)
        min = a[i];
        if (a[i] > max)
        max = a[i];
    }
    int range = max - min + 1;
    int* countA = (int*)calloc(range, sizeof(int));
    if (countA == NULL)
    {
        perror ("calloc failln"); exit (-1);
    }   

    for (int i=0;i<n;++i)
    { 
        countA[a[i]-min]++;
    }

    int k = 0;
    for (int j = 0; j <range; ++j)
    {
        while (countA[j]--)
        {
            a[k++] = j + min;
        }
    }
free (countA);
}








//打印
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void Swap(int* a,int*b)
{
    int t=*a;
    *a=*b;
    *b=t;
}